package main

import "fmt"

func main() {
	fmt.Println(partition("aab"))
}

// 第一重，如何抽象为组合问题
// 第二重，如何模拟切线 开始索引index是子串第一个元素，当前遍历的位置i是最后一个元素 子串即s[index:i+1]
// 第三重，切割问题中递归如何中止 i取到s最后一个元素后中止
// 第四重，在递归中如何截取子串
func partition(s string) [][]string {
	var res [][]string
	var list []string
	var helper func(index int)
	helper = func(index int) {
		if index == len(s) {
			tmp := make([]string, len(list))
			copy(tmp, list)
			res = append(res, tmp)
			return
		}

		for i := index; i < len(s); i++ {
			str := s[index : i+1]
			if !isP(str) {
				continue
			}

			list = append(list, str)
			helper(i + 1)
			list = list[:len(list)-1]
		}
	}
	helper(0)
	return res
}

func isP(s string) bool {
	i, j := 0, len(s)-1
	for i <= j {
		if s[i] != s[j] {
			return false
		}
		i++
		j--
	}
	return true
}
